package com.zq.solution.algorithm.sort;

/**
 * @ClassName ArraySort
 * @Description 数组排序
 * @Author ZQ
 * @Date 2020/10/16 9:03
 * @Version 1.0
 */
public class BaseSort {
    public static int[] bubblingSort(int[] arr){//冒泡排序
        if (arr == null || arr.length < 2) return arr;
        for (int i = 1; i < arr.length; i++){
            boolean flag = true;
            for (int j = 0; j < arr.length- i; j++){
                if (arr[j] > arr[j + 1]){
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                    flag = false;
                }
            }
            if (flag) break;
            System.out.print("第"+i+"轮交换完之后的结果：");
            printArr(arr);
        }

        return arr;
    }

    public static int[] chooseSort(int[] arr){//选择排序
        if (arr == null || arr.length < 2) return arr;
        for (int i = 0; i < arr.length - 1; i++){
            int min = i;
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[min]) min = j;
            }
            if (i != min){
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
            System.out.print("第"+(i + 1)+"轮交换完之后的结果：");
            printArr(arr);
        }
        return arr;
    }
    public static int[] insertSort(int[] arr){//插入
        if (arr == null || arr.length < 2) return arr;
        int j;
        for (int i = 1; i < arr.length; i++){
            j = i;
            int tmp = arr[i];
            while (j > 0 && tmp < arr[j - 1]){
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = tmp;

        }
        printArr(arr);
        return arr;
    }
    public static void printArr(int[] arr){
        for (Integer num : arr){
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        insertSort(new int[]{6,71,72,8,73,75,14,80,18,83,20,87,24,25,27,93,29,97,99,100,37,102,103,42,107,47,112,49,115,116,55,121,123,124,125,126,63});
        System.out.println("====================================");
        insertSort(new int[]{748,699,47,123,14,478,593,401,396,75,965,795,544,691,981,711,470,172,223,690,100,934,260,733,83,392,424,739,160,648,910,528,137,115,285,578,287,669,534,469,282,283,701,330,994,419,575,365,916,188,784,873,337,308,895,313,672,277,518,6,395,196,246,586,331,547,382,103,530,590,899,732,180,571,985,613,99,922,538,24,263,220,584,961,143,588,55,715,178,977,832,124,896,834,655,712,903,244,862,861,738,311,888,661,158,724,374,431,957,387,80,798,93,522,656,449,499,216,357,340,409,726,346,606,316,153,943,667,369,73,214,603,513,164,851,756,625,102,877,838,687,209,567,771,126,558,146,281,125,510,298,750,533,439,902,727,258,116,351,780,138,323,8,301,144,842,626,243,789,734,429,786,130,921,824,704,49,956,608,266,919,181,526,430,252,483,112,233,642,482,905,997,446,289,453,757,18,980,42,886,602,391,259,407,381,968,827,107,411,694,815,27,914,175,731,554,176,20,232,184,569,325,932,505,148,444,796,936,829,682,947,349,754,793,496,251,72,610,646,828,946,950,582,195,231,29,458,583,703,291,237,540,666,204,952});
    }
}
